import java.util.*;

public class test {
    //前K个高频单词：前K个出现次数最多的单词
    public static List<String> topKFrequent(String[] words, int k) {
        //统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.get(s) == null) {
                map.put(s, 1);
            }else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        //建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //如果出现次数相同，则按照字典大小来比较
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        List<String> list = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            list.add(minHeap.poll().getKey());
        }

        //倒置
        Collections.reverse(list);
        return list;

    }


    //坏键盘打字
    public static void func(String str1, String str2) {
        HashSet<Character> set = new HashSet<>();
        for(char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }

        HashSet<Character> set1 = new HashSet<>();
        for(char ch : str1.toUpperCase().toCharArray()) {
            if(!set.contains(ch) && !set1.contains(ch)) {
                System.out.print(ch);
                set1.add(ch);
            }
        }
    }

    public static void main(String[] args) {
        String s1 = "7_This_is_a_test";
        String s2 = "_hs_s_a_es";
        func(s1, s2);
    }
    public static void main1(String[] args) {
        String[] words = new String[] {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 3;
        List<String> list = topKFrequent(words, k);
    }
}
